package lhz.algorithm.chapter.six;
/**
 * HEAP-DELETE，《算法导论》习题6.5-7
 * 习题原文：
 * The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an
 * implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.
 * @author lihzh(苦逼coder)
 */
public class HeapDelete {
	
	//初始化MaxHeap堆
	private static int[] heap = new int[] {11, 7, 10, 6, 5, 9, 1, 4, 3, 2, 8};
	//初始化堆大小
	private static int heapSize = heap.length;

	public static void main(String[] args) {
		//简单测试代码
		heapDelete(9);
		printHeap();
		heapDelete(3);
		printHeap();
		heapDelete(6);
		printHeap();
		heapDelete(3);
		printHeap();
		heapDelete(5);
		printHeap();
		heapDelete(3);
		printHeap();
		heapDelete(1);
		printHeap();
	}
	
	/**
	 * 删除堆中指定元素，利用<code>MaxHeapify</code>算法（复杂度：O(lgn)）
	 * 复杂度分析：
	 * 当删除的索引等于1或者交换过来的元素小于其父元素的时候，调用MaxHeapify
	 * 算法，重新构造堆，此时复杂度为：O(lgn)
	 * 当大于父元素的时候，递归交换其与父元素的位置，此时复杂度仍为：O(lgn)
	 * 综上，复杂度为：O(lgn)
	 * @param heapIndex 堆中元素索引(1-heapSize)
	 */
	private static void heapDelete(int heapIndex) {
		if (heapIndex > heapSize) {
			System.err.println("索引超过堆中最大元素个数，元素不在堆中！");
			return;
		}
		//数组索引比堆索引小1
		int arrayIndex = heapIndex - 1;
		int key = heap[arrayIndex]; 
		heap[arrayIndex] =  heap[heapSize-1];
		heap[heapSize-1] = key;
		heapSize--;
		if (heapIndex > 1) {
			int parentIndex = heapIndex / 2;
			if (heap[arrayIndex] > heap[parentIndex-1]) {
				while (parentIndex > 1
						&& heap[arrayIndex] > heap[parentIndex-1]) {
					int temp = heap[arrayIndex];
					heap[arrayIndex] = heap[parentIndex-1];
					heap[parentIndex-1] = temp;
					arrayIndex = parentIndex - 1;
					parentIndex = parentIndex / 2;
				}
			}
		} else {
			maxHeapify(heapIndex);
		}
	}
	
	/**
	 * 之前实现的<code>MaxHeapify</code>算法
	 * @param array
	 * @param index
	 */
	private static void maxHeapify(int index) {
		int l = index * 2;
		int r = l + 1;
		int largest;
		//如果左叶子节点索引小于堆大小，比较当前值和左叶子节点的值，取值大的索引值
		if (l <= heapSize && heap[l-1] > heap[index-1]) {
			largest = l;
		} else {
			largest = index;
		}
		//如果右叶子节点索引小于堆大小，比较右叶子节点和之前比较得出的较大值，取大的索引值
		if (r <= heapSize && heap[r-1] > heap[largest-1]) {
			largest = r;
		}
		//交换位置，并继续递归调用该方法调整位置。
		if (largest != index) {
			int temp = heap[index-1];
			heap[index-1] = heap[largest-1];
			heap[largest-1] = temp;
			maxHeapify(largest);
		}
	}
	
	private static void printHeap() {
		for (int i = 0; i < heapSize; i++) {
			System.out.print(heap[i] + " ");
		}
		System.out.println();
	}
	
	
}
